import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树 {

    static TreeNode root = new TreeNode(0);

    static {
        int n = 10;
        int[] nums = new int[n];
        Queue<TreeNode> queue = new LinkedList<>();
        root.left = new TreeNode(1);
        queue.add(root);
        for (int i = 1; i < n; i += 2) {
            TreeNode poll = queue.poll();
            poll.left = new TreeNode(i);
            poll.right = new TreeNode(i + 1);
            queue.add(poll.left);
            queue.add(poll.right);
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root != null)
            dfs1(res, root);
        return res;
    }

    public static void dfs1(List<Integer> res, TreeNode root) {
        if (root == null)
            return;
        dfs1(res, root.left);
        res.add(root.val);
        dfs1(res, root.right);
    }

    public boolean isValidBST(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root != null) {
            dfs1(res, root);
            for (int i = 1; i < res.size(); i++)
                if (res.get(i) <= res.get(i - 1))
                    return false;
        }
        return true;
    }

    public static boolean dfs2(TreeNode root, int last) {
        if (root == null)
            return true;


        return false;
    }

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p != null)
            if (q == null)
                return false;
            else return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        return q == null;
    }

    public static void main(String[] args) {
        System.out.println(inorderTraversal(root));
    }
}
